1. Field of the Invention (Technical Field)
The present invention relates to methods and software for generating quadrilateral or hexahedral finite element meshes, particularly all-quadrilateral or all-hexahedral finite element meshes.
2. Description of Related Art
Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-a-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes.
The search for a reliable all-quadrilateral and all-hexahedral meshing algorithm continues. Many researchers have abandoned the search, relying upon the widely available and highly robust tetrahedral meshing algorithms, such as P.-L. George, H. Borouchaki, Delaunay Triangulation and Meshing: Application to Finite Elements, Editions HERMES, Paris (1998). However, quad or hex meshes are still preferable for many applications, and depending on the solver, still required.
For all-quadrilateral meshing, Paving and its many permutations have proven reliable. T. D. Blacker, M. B. Stephenson. “Paving: A New Approach to Automated Quadrilateral Mesh Generation”, International Journal for Numerical Methods in Engineering, 32, 811-847 (1991); S. J. Owen, M. L. Staten, S. A. Canann, S. Siagal, “Q-Morph: An Indirect Approach to Advancing Front Quad Meshing”, International Journal for Numerical Methods in Engineering, 44, 1317-1340 (1999); and D. R. White, P. Kinney, “Redesign of the Paving Algorithm: Robustness Enhancements through Element by Element Meshing”, Proc. 6th Int. Meshing Roundtable, 323-335 (1997). Paving starts with pre-meshed boundary edges which are classified into fronts and advanced inward. As fronts collide, they are seamed, smoothed, and transitioned until only a small unmeshed void remains (usually 6-sided or smaller). Then a template is inserted into this void resulting in quadrilaterals covering the entire surface.
Paving's characteristic of maintaining high quality, boundary-aligned rows of elements is what has made it a successful approach to quad meshing. In addition, because of its ability to transition in element size, Paving is able to match nearly any boundary edge mesh.
There have been many attempts to extend Paving to arbitrary three-dimensional (3D) solid geometry. While valuable contributions to the literature, these attempts have not resulted in reliable general algorithms for hexahedral meshing. Plastering was one of the first attempts. S. A. Canann, Plastering: A New Approach to Automated 3-D Hexahedral Mesh Generation, American Institute of Aeronautics and Astronics (1992); J. Hipp, R. Lober, “Plastering: All-Hexahedral Mesh Generation Through Connectivity Resolution”, Proc. 3rd International meshing Roundtable (1994); S. A. Canann, “Plastering and Optismoothing: New Approaches to Automated 3D Hexahedral Mesh Generation and Mesh Smoothing”, Ph.D. Dissertation, Brigham Young University, Provo, Utah, USA (1991); and T. D. Blacker, R. J. Meyers, “Seams and Wedges in Plastering: A 3D Hexahedral Mesh Generation Algorithm”, Engineering With Computers, 2, 83-93 (1993). In Plastering, the bounding surfaces of the solid are quad meshed, fronts are determined and then advanced inward. However, once opposing fronts collide, the algorithm frequently has deficiencies. Unless the number, size, and orientation of the quadrilateral faces on opposing fronts match, Plastering is rarely able to resolve the unmeshed voids.
Many creative attempts have been made to resolve this unmeshed void left behind by plastering. Since arbitrary 3D voids can be robustly filled with tets, the idea of plastering in a few layers, followed by tet-meshing the remaining void was attempted. D. Dewhirst, S. Vangavolu, H. Wattrick, “The Combination of Hexahedral and Tetrahedral Meshing Algorithms”, Proc. 4th International Meshing Roundtable, 291-304 (1995); and R. Meyers, T. Tautges, P. Tuchinsky, “The ‘Hex-Tet’ Hex-Dominant Meshing Algorithm as Implemented in CUBIT”, Proc. 7th International Meshing Roundtable, 151-158 (1998). Transitions between the tets and hexes were done with Pyramids and multi-point constraints. Hexahedra Conformability”, Trends in Unstructured Mesh Generation, AMD Vol. 220, 123-129, ASME (1997). The Geode-Template provided a method of generating an all-hex mesh by refining both the hexes and tets. R. W. Leland, D. Melander, R. Meyers, S. Mitchell, T. Tautges, “The Geode Algorithm: Combining Hex/Tet Plastering, Dicing and Transition Elements for Automatic, All-Hex Mesh Generation”, Proc 7th International Meshing Roundtable, 515-521 (1998). However, this required an additional refinement of the entire mesh resulting in meshes much larger than required. In addition, the Geode-Template was unable to provide reasonable element quality.
A draw-back of Paving is the need for expensive intersection calculations. An alternative to Paving called Q-Morph, White, supra, eliminated the need for intersection calculations by first triangle meshing the surface. This triangle mesh is then “transformed” into a quad mesh. Using a similar advancing front technique to paving, triangles are locally reconnected, repositioned, and combined to form quads. Q-Morph is able to form high-quality quadrilateral elements with similar characteristics to paving. Q-Morph has proven to be a robust and reliable quad meshing algorithm in common use in several commercial meshing packages.
An attempt at extending Q-Morph to a hex-dominant meshing algorithm was done with H-Morph. S. J. Owen, “Non-Simplical Unstructured Mesh Generation”, Ph.D. Dissertation, Carnegie Mellon University, Pittsburgh, Pa., USA (1999). This algorithm takes an existing tetrahedral mesh and applies local connectivity transformations to the elements. Groups of tetrahedral are then combined to form high-quality hexahedra. The advancing front approach was also used for ordering and prioritizing tetrahedral transformations. Although H-Morph had the desirable characteristics of regular layers near the boundaries, it was unable to reliably resolve the interior regions to form a completely all-hex mesh since it also attempted to honor a pre-meshed quad boundary.
Recognizing the difficulty of defining the full connectivity of a hex mesh using traditional geometry-based advancing front approaches, the Whisker-Weaving algorithm attempted to address the problem from a purely topological approach. T. J. Tautges, T. Blacker, S. Mitchell, “The Whisker-Weaving Algorithm: A Connectivity Based Method for Constructing All-Hexahedral Finite Element Meshes”, International Journal for Numerical Methods in Engineering, 39, 3327-3349 (1996); P. Murdoch, S. Benzley, “The Spatial Twist Continuum”, Proc. 4th International Meshing Roundtable, 243-251 (1995); and N. T. Folwell, S. A. Mitchell, “Reliable Whisker Weaving via Curve Contraction,” Proc. 7th International Meshing Roundtable, 365-378 (1998). It attempts to first generate the complete dual of the mesh, from which the primal, or hex elements, are readily obtainable. Although whisker-weaving can in most cases generate a successful dual topology, resulting hex elements are often poorly shaped or inverted.
Plastering, H-Morph, Whisker Weaving and all of their permutations are classified as Outside-In-Methods. They start with a pre-defined boundary quad mesh and then attempt to use that to define the hex connectivity on the inside. Another class of Hex meshing algorithms can be classified as Inside-Out methods. R. Schneiders, R. Schindler, R. Weiler, “Octree-Based Generation of Hexahedral Element Meshes”, Proc. 5th International Meshing Roundtable, 205-217 (1996); P. Kraft, “Automatic Remeshing with Hexahedral Elements: Problems, Solutions and Applications”, Proc. 8th International Meshing Roundtable, 357-368 (1999); and G. D. Dhondt, “Unstructured 20-Node Brick Element Meshing”, Proc. 8th International Meshing Roundtable, 369-376 (1999). These algorithms fill the inside of the solid with elements first, often using an octree-based grid. This grid is then adapted to fit the boundary. These methods place high quality elements on the interior of the volume, however, they typically generate extremely poor quality elements on the boundary. In addition, traditional Inside-Out methods are unable to mesh assemblies with conformal meshes. These inside-out methods seem particularly popular with the metal forming industry, but of less appeal in structural mechanics applications.
Sweeping based methods are among the most widely used hexahedral based meshing algorithms in industry today. T. D. Blacker, “The Cooper Tool”, Proc. 5th International Meshing Roundtable, 13-29 (1996); Mingwu Lai, “Automatic Hexahedral Mesh Generation by Generalized Multiple Source to Multiple Target Sweeping”, Ph.D. Dissertation, Brigham Young University, Provo, Utah, USA (1998); and M. L. Staten, S. Canann, S. Owen, “BMSweep: Locating Interior Nodes During Sweeping”, Proc. 7th International Meshing Roundtable, 7-18 (1998). Sweeping, however, applies only to solids which are 2.5D, or solids which can be decomposed into 2.5D sub-regions. There has been a considerable amount of research in sweeping and many successful implementations have been published. It is typically quite simple to decompose and sweep simple to medium complexity solids. However, as more complexity is added to the solid model, the task of decomposing the solids into 2.5D sub-regions can be daunting, and in some regards, an art-form requiring significant creativity and experience.
Advancing front methods have proven ideal for triangle, quadrilateral and even tetrahedral meshes. They have been successful in these arenas because of the smaller number of constraints imposed by the connectivity of these simple element shapes. Hexahedral meshes, on the other hand, must maintain a connectivity of eight nodes, 12 edges, and six faces per element, with strict constraints on warping and skewness. As a result, unlike tetrahedral meshes, minor local changes to the connectivity of a hex mesh can have severe consequences to the global mesh structure. For this reason, current hexahedral advancing front methods where the boundary is prescribed apriori have rarely succeeded for general geo-metric configurations.
Current advancing front methods, while having the high ideal of maintaining the integrity of a prescribed boundary mesh, frequently fail because the very boundary mesh they are attempting to maintain over-constrains the problem, creating a predicament which can be intractable.
To resolve this issue, the present invention introduces a new concept, known as Unconstrained Plastering, as presented in M. L. Staten, S. J. Owen, T. D. Blacker, “Unconstrained Paving & Plastering: A New Idea for All Hexahedral Mesh Generation,” Proc. 14th Int. Meshing Roundtable, 399-416 (Sep. 8, 2005). With this approach, one relaxes the constraint of prescribing a boundary apriori quad mesh. While still maintaining the desirable characteristics of advancing front meshes, Unconstrained Plastering is free to define the topology of its boundary mesh as a consequence of the interior meshing process. It is understood that not prescribing an apriori boundary quad mesh can have implications on the traditional bottom-up approach to mesh generation. These implications, however, are significantly outweighed by the prospect of automating the all-quad or all-hex mesh generation process through a more top-down approach to the problem that Unconstrained Plastering offers.